package dynamicStudy;

public class DynamicStudy02 {

    /**
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     *
     * 问总共有多少条不同的路径？
     *
     * 该问题是计数问题
     *
     * 用二维数组解决计数问题
     * @param args
     */
    public static void main(String[] args) {
        int i = uniquePaths(1, 3);
        System.out.println(i);
    }

    public static int uniquePaths(int m, int n){
        //确定数组
        int[][] f = new int[m][n];
        //初始化
        int i, j;
        //初始化第1列
        for (i = 0; i < m; i++){
            f[i][0] = 1;
        }
        for (j = 0; j < n; j++){
            f[0][j] = 1;
        } //初始化也可以放进循环当中
        for (i = 1; i < m; i++){
            for (j = 1; j < n; j++){
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }

        return f[m - 1][n - 1];

    }
}
